package Quene;

import Stack.SeqStack;
import Stack.Stack;

public class wiring {
    //先广度遍历找出从起点起到达不同位置的距离
    public String Solution(Point start, Point end, int[][] circuit) throws Exception {
        Point now = start;
        circuit[start.getX()][start.getY()] = 1;
        //排除起点或终点位于墙内的情况
        if (circuit[start.getX()][start.getY()] == -1 || circuit[end.getX()][end.getY()] == -1)
            throw new Exception("起点或终点位于墙中");
        SeqQuene<Point> pointSeqQuene = new SeqQuene<Point>();
        pointSeqQuene.add(now);
        while (!(now.getX() == end.getX() && now.getY() == end.getY())) {

            //进行四个方向的查询，如果可通行就将该位置标记为相应的步距
            if (now.getY() - 1 >= 0 && circuit[now.getX()][now.getY() - 1] == 0) {
                pointSeqQuene.add(new Point(now.getX(), now.getY() - 1));
                circuit[now.getX()][now.getY() - 1] = circuit[now.getX()][now.getY()] + 1;
            }
            if (now.getX() - 1 >= 0 && circuit[now.getX() - 1][now.getY()] == 0) {
                pointSeqQuene.add(new Point(now.getX() - 1, now.getY()));
                circuit[now.getX() - 1][now.getY()] = circuit[now.getX()][now.getY()] + 1;
            }
            if (now.getY() + 1 < circuit.length && circuit[now.getX()][now.getY() + 1] == 0) {
                pointSeqQuene.add(new Point(now.getX(), now.getY() + 1));
                circuit[now.getX()][now.getY() + 1] = circuit[now.getX()][now.getY()] + 1;
            }
            if (now.getX() + 1 < circuit.length && circuit[now.getX() + 1][now.getY()] == 0) {
                pointSeqQuene.add(new Point(now.getX() + 1, now.getY()));
                circuit[now.getX() + 1][now.getY()] = circuit[now.getX()][now.getY()] + 1;
            }
            //如果队列已经为空但还没到达终点，说明起点和终点间不存在相通的路线
            if (pointSeqQuene.isEmpty()) throw new Exception("找不到能够从起点到终点的路径");
            now = pointSeqQuene.poll();
        }
        String str = "从"+start+"到"+end+"的最短路径为";
        Stack<Point> road = new SeqStack<Point>();
        //回溯算法
        while (circuit[now.getX()][now.getY()] != 1) {
            if (circuit[now.getX() - 1][now.getY()] == circuit[now.getX()][now.getY()] - 1) {
                Point temp = new Point(now.getX() - 1, now.getY());
                road.push(temp);
                now = temp;
                continue;
            }
            if (circuit[now.getX()][now.getY() - 1] == circuit[now.getX()][now.getY()] - 1) {
                Point temp = new Point(now.getX(), now.getY() - 1);
                road.push(temp);
                now = temp;
                continue;
            }
            if (circuit[now.getX() + 1][now.getY()] == circuit[now.getX()][now.getY()] - 1) {
                Point temp = new Point(now.getX() + 1, now.getY());
                road.push(temp);
                now = temp;
                continue;
            }
            if (circuit[now.getX()][now.getY() + 1] == circuit[now.getX()][now.getY()] - 1) {
                Point temp = new Point(now.getX(), now.getY() + 1);
                road.push(temp);
                now = temp;
            }
        }
        while (!road.isEmpty()) {
            str += road.pop() + "→";
        }
        str += end;
        return str;
    }
}